if (!require("BiocManager", quietly = TRUE))
install.packages("BiocManager")
BiocManager::install("curatedTCGAData");
Update all/some/none? [a/s/n]:
n
BiocManager::install("TCGAutils");
Update all/some/none? [a/s/n]:
n
BiocManager::install("TCGAbiolinks");
Update all/some/none? [a/s/n]:
n
install.packages("SNFtool");
Error in install.packages : Updating loaded packages
install.packages("NetPreProc");
Error in install.packages : Updating loaded packages
library("curatedTCGAData");
library("TCGAbiolinks");
library("TCGAutils");
library("SNFtool")
library("NetPreProc");
library("cluster");
Download Prostate
adenocarcinoma dataset
assays <- c("miRNASeqGene", "RNASeq2Gene", "RPPAArray");
mo <- curatedTCGAData(diseaseCode = "PRAD",
assays = assays,
version = "2.1.1", dry.run=FALSE);
snapshotDate(): 2023-10-24
Working on: PRAD_RNASeq2Gene-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_RPPAArray-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_miRNASeqGene-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_colData-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_sampleMap-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
Working on: PRAD_metadata-20160128
see ?curatedTCGAData and browseVignettes('curatedTCGAData') for documentation
loading from cache
harmonizing input:
removing 5189 sampleMap rows not in names(experiments)
mo
A MultiAssayExperiment object of 3 listed
experiments with user-defined names and respective classes.
Containing an ExperimentList class object of length 3:
[1] PRAD_RNASeq2Gene-20160128: SummarizedExperiment with 20501 rows and 550 columns
[2] PRAD_RPPAArray-20160128: SummarizedExperiment with 195 rows and 352 columns
[3] PRAD_miRNASeqGene-20160128: SummarizedExperiment with 1046 rows and 547 columns
Functionality:
experiments() - obtain the ExperimentList instance
colData() - the primary/phenotype DataFrame
sampleMap() - the sample coordination DataFrame
`$`, `[`, `[[` - extract colData columns, subset, or experiment
*Format() - convert into a long or wide DataFrame
assays() - convert ExperimentList to a SimpleList of matrices
exportClass() - save data to flat files
Data
pre-processing
Consider only primary solid tumors Analyte information missing from
PRAD_RPPAArray (20th position) that causes inconsistent barcode lengths
in MultiArrayExperiment object mo (but doesn’t cause
problems for the code below).
primary <- TCGAutils::TCGAsampleSelect(colnames(mo), c("01"));
mo <- mo[,primary,]
Check for replicates for same patient (first 12 characters) No
replicates present in mo.
check_rep <- anyReplicated(mo);
print(check_rep)
PRAD_RNASeq2Gene-20160128 PRAD_RPPAArray-20160128 PRAD_miRNASeqGene-20160128
FALSE FALSE FALSE
Remove FFPE samples (frozen tissue is better preseved)
no_ffpe <- which(as.data.frame(colData(mo))$patient.samples.sample.is_ffpe == "no");
as.data.frame(colData(mo))
mo <- mo[, no_ffpe, ];
Consider samples having all considered omics data
complete <- intersectColumns(mo);
ExpressionList → simple list of matrices
complete <- assays(complete)
print(dim(complete[[1]]))
[1] 20501 348
Transpose all three matrices, obtaining samples \(\times\) features
complete <- lapply(complete,FUN=t)
Remove features having missing values (no missing values in the
current dataset)
for (i in 1:length(complete)){
#print(dim(complete[[i]]))
complete[[i]] <- complete[[i]][,colSums(is.na(complete[[i]]))==0]
#print(dim(complete[[i]]))
}
Select features having more variance across samples because they
bring more information.
nf <- 100;
for(i in 1:length(complete)){
idx <- caret::nearZeroVar(complete[[i]])
message(paste("Removed ", length(idx), "features from", names(complete)[i]));
if(length(idx) != 0){
complete[[i]] <- complete[[i]][, -idx];
}
if(ncol(complete[[i]]) <= nf) next
vars <- apply(complete[[i]], 2, var);
idx <- sort(vars, index.return=TRUE, decreasing = TRUE)$ix;
complete[[i]] <- complete[[i]][, idx[1:nf]];
}
Removed 1334 features from PRAD_RNASeq2Gene-20160128
Removed 0 features from PRAD_RPPAArray-20160128
Removed 471 features from PRAD_miRNASeqGene-20160128
Standardize features with z-score
zscore <- function(data){
zscore_vec <- function(x) { return ((x - mean(x)) / sd(x))}
data <- apply(data, 2, zscore_vec)
return(data)
}
complete <- lapply(complete, zscore);
Clean barcodes retaining only “Project-TSS-Participant” (first 12
characters)
for(v in 1:length(complete)){
rownames(complete[[v]]) <- substr(rownames(complete[[v]]), 1, 12);
}
Download disease
subtypes
subtypes <- as.data.frame(TCGAbiolinks::PanCancerAtlas_subtypes())
subtypes <- subtypes[subtypes$cancer.type == "PRAD", ];
# Retain only primary solid tumors and select samples in common with omics data
# (in the same order):
subtypes <- subtypes[TCGAutils::TCGAsampleSelect(subtypes$pan.samplesID, "01"), ];
sub_select <- substr(subtypes$pan.samplesID,1,12) %in% rownames(complete[[1]]);
subtypes <- subtypes[sub_select, ];
We consider only samples in the omics data in complete
for which also subtype data is present in subtypes
rownames(subtypes) <- substr(subtypes$pan.samplesID, 1, 12);
for (i in 1:length(complete))
complete[[i]] <- complete[[i]][rownames(subtypes),]
# Print number of samples for each subtype:
table(subtypes$Subtype_Integrative);
1 2 3
60 83 105
Check subtype &
omics data order
count <- 0
for(i in 1:length(rownames(subtypes))){
if(rownames(subtypes)[i] != rownames(complete[[1]])[i])
count <- count + 1
}
count
[1] 0
All patients/samples are in the same order in both the datasets. #
Multi-omics data integration Similarity matrices for each data source
using exponential euclidian distance (affinity matrix).
Integration through
SNF
Integration of the matrices using Similarity Network Fusion
t number of iterations _K_ number of neighbours to
consider to compute local similarity matrix
Integration through
average
Integration through average of matrices
for (i in 1:length(W_list))
plot(W_list[[i]],xlim=c(0,0.01),ylim=c(0,0.01))



Disease subtype
discovery with PAM
Number of clusters.
Each data source
Convert similarity matrix into a distance matrix. The similarities
are normalized in the range &$ using min-max normalization before
conversion into distances.
# Convert similarity matrix into a distance matrix. The similarities
# are normalized in the range [0, 1] using min-max normalization before
# conversion into distances.
dist <- list()
D <- list()
for (i in 1:length((W_list))){
dist[[i]] <- 1 - NetPreProc::Max.Min.norm(W_list[[i]])
D[[i]] <- as.dist(dist[[i]])
}
for (i in 1:length((W_list)))
pam.res <- pam(D[[i]], k=k)
Integrated data
through mean
dist_mean <- 1 - NetPreProc::Max.Min.norm(W_int_mean);
D_mean <- as.dist(dist_mean);
pam.res <- pam(D_mean, k=k);
Integrated data
through SNF
dist_SNF <- 1 - NetPreProc::Max.Min.norm(W_int_SNF);
D_SNF <- as.dist(dist_SNF);
# Apply clustering algorithms on integrated matrix:
pam.res <- pam(D_SNF, k=k);
#Disease subtype discovery with spectral clustering (Consider
distance matrix calculated above) ## Integrated data through SNF
k <- length(unique(subtypes$Subtype_Integrative));
sc.res <- SNFtool::spectralClustering(W_int_SNF, K=k)
#to have uniform type
pam.sc.res <- pam(sc.res,k=k)
sessionInfo()
LS0tDQp0aXRsZTogIkJpb2luZm9ybWF0aWNzIHByb2plY3QgeWVhciAyMDIzLzIwMjQiDQphdXRob3I6ICJMdWNpYSBBbm5hIE1lbGxpbmkiDQpkYXRlOg0KI2JpYmxpb2dyYXBoeTogcmVmZXJlbmNlcy5iaWINCm91dHB1dDogDQogICAgaHRtbF9ub3RlYm9vazoNCiAgICAgICAgdG9jOiB0cnVlDQogICAgICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQ0KICAgICAgICB0b2NfZmxvYXQ6IHRydWUNCiAgICAgICAgdGhlbWU6IGNlcnVsZWFuDQogICAgICAgIGZpZ19jYXB0aW9uOiB0cnVlDQotLS0NCg0KDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KaWYgKCFyZXF1aXJlKCJCaW9jTWFuYWdlciIsIHF1aWV0bHkgPSBUUlVFKSkNCiAgICBpbnN0YWxsLnBhY2thZ2VzKCJCaW9jTWFuYWdlciIpDQoNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJjdXJhdGVkVENHQURhdGEiKTsNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJUQ0dBdXRpbHMiKTsNCkJpb2NNYW5hZ2VyOjppbnN0YWxsKCJUQ0dBYmlvbGlua3MiKTsNCg0KaW5zdGFsbC5wYWNrYWdlcygiU05GdG9vbCIpOw0KaW5zdGFsbC5wYWNrYWdlcygiTmV0UHJlUHJvYyIpOw0KYGBgDQoNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpsaWJyYXJ5KCJjdXJhdGVkVENHQURhdGEiKTsNCmxpYnJhcnkoIlRDR0FiaW9saW5rcyIpOw0KbGlicmFyeSgiVENHQXV0aWxzIik7DQoNCmxpYnJhcnkoIlNORnRvb2wiKQ0KbGlicmFyeSgiTmV0UHJlUHJvYyIpOw0KbGlicmFyeSgiY2x1c3RlciIpOw0KYGBgDQojIERvd25sb2FkIFByb3N0YXRlIGFkZW5vY2FyY2lub21hIGRhdGFzZXQjDQo8IS0tIG1pUk5BU2VxR2VuZSAgICAgICAgICAgICAgR2VuZS1sZXZlbCBsb2cyIFJQTSBtaVJOQSBleHByZXNzaW9uIHZhbHVlcw0KPD5STkFTZXEyR2VuZSAgICAgICAgICAgICAgIFJTRU0gVFBNIGdlbmUgZXhwcmVzc2lvbiB2YWx1ZXMNCjw+UlBQQUFycmF5ICAgICAgICAgICAgICAgICBSZXZlcnNlIFBoYXNlIFByb3RlaW4gQXJyYXkgbm9ybWFsaXplZCBwcm90ZWluIGV4cHJlc3Npb24gdmFsdWVzIC0tPg0KYGBge3J9DQoNCmFzc2F5cyA8LSBjKCJtaVJOQVNlcUdlbmUiLCAiUk5BU2VxMkdlbmUiLCAiUlBQQUFycmF5Iik7DQptbyA8LSBjdXJhdGVkVENHQURhdGEoZGlzZWFzZUNvZGUgPSAiUFJBRCIsIA0KICAgICAgICAgICAgICAgICAgICAgICAgYXNzYXlzID0gYXNzYXlzLA0KICAgICAgICAgICAgICAgICAgICAgICAgdmVyc2lvbiA9ICIyLjEuMSIsIGRyeS5ydW49RkFMU0UpOw0KYGBgDQoNCmBgYHtyIG1lc3NhZ2U9VFJVRX0NCm1vDQpgYGANCiMgRGF0YSBwcmUtcHJvY2Vzc2luZw0KQ29uc2lkZXIgb25seSBwcmltYXJ5IHNvbGlkIHR1bW9ycw0KQW5hbHl0ZSBpbmZvcm1hdGlvbiBtaXNzaW5nIGZyb20gUFJBRF9SUFBBQXJyYXkgKDIwdGggcG9zaXRpb24pIHRoYXQgY2F1c2VzIGluY29uc2lzdGVudCBiYXJjb2RlIGxlbmd0aHMgaW4gTXVsdGlBcnJheUV4cGVyaW1lbnQgb2JqZWN0ICBgYGBtb2BgYCAoYnV0IGRvZXNuJ3QgY2F1c2UgcHJvYmxlbXMgZm9yIHRoZSBjb2RlIGJlbG93KS4NCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpwcmltYXJ5IDwtIFRDR0F1dGlsczo6VENHQXNhbXBsZVNlbGVjdChjb2xuYW1lcyhtbyksIGMoIjAxIikpOw0KbW8gPC0gbW9bLHByaW1hcnksXQ0KYGBgDQpDaGVjayBmb3IgcmVwbGljYXRlcyBmb3Igc2FtZSBwYXRpZW50IChmaXJzdCAxMiBjaGFyYWN0ZXJzKQ0KTm8gcmVwbGljYXRlcyBwcmVzZW50IGluIGBgYG1vYGBgLg0KYGBge3J9DQpjaGVja19yZXAgPC0gYW55UmVwbGljYXRlZChtbyk7DQpwcmludChjaGVja19yZXApDQpgYGANClJlbW92ZSBGRlBFIHNhbXBsZXMgKGZyb3plbiB0aXNzdWUgaXMgYmV0dGVyIHByZXNldmVkKQ0KYGBge3J9DQpub19mZnBlIDwtIHdoaWNoKGFzLmRhdGEuZnJhbWUoY29sRGF0YShtbykpJHBhdGllbnQuc2FtcGxlcy5zYW1wbGUuaXNfZmZwZSA9PSAibm8iKTsNCmFzLmRhdGEuZnJhbWUoY29sRGF0YShtbykpDQptbyA8LSBtb1ssIG5vX2ZmcGUsIF07DQpgYGANCkNvbnNpZGVyIHNhbXBsZXMgaGF2aW5nIGFsbCBjb25zaWRlcmVkIG9taWNzIGRhdGENCmBgYHtyfQ0KY29tcGxldGUgPC0gaW50ZXJzZWN0Q29sdW1ucyhtbyk7DQpgYGANCkV4cHJlc3Npb25MaXN0IOKGkiBzaW1wbGUgbGlzdCBvZiBtYXRyaWNlcw0KYGBge3J9DQpjb21wbGV0ZSA8LSBhc3NheXMoY29tcGxldGUpDQpwcmludChkaW0oY29tcGxldGVbWzFdXSkpDQpgYGANClRyYW5zcG9zZSBhbGwgdGhyZWUgbWF0cmljZXMsIG9idGFpbmluZyBzYW1wbGVzICRcdGltZXMkIGZlYXR1cmVzDQpgYGB7cn0NCmNvbXBsZXRlIDwtIGxhcHBseShjb21wbGV0ZSxGVU49dCkNCmBgYA0KUmVtb3ZlIGZlYXR1cmVzIGhhdmluZyBtaXNzaW5nIHZhbHVlcyAobm8gbWlzc2luZyB2YWx1ZXMgaW4gdGhlIGN1cnJlbnQgZGF0YXNldCkNCmBgYHtyfQ0KZm9yIChpIGluIDE6bGVuZ3RoKGNvbXBsZXRlKSl7DQogICNwcmludChkaW0oY29tcGxldGVbW2ldXSkpDQogIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVssY29sU3Vtcyhpcy5uYShjb21wbGV0ZVtbaV1dKSk9PTBdDQogICNwcmludChkaW0oY29tcGxldGVbW2ldXSkpDQp9DQpgYGANClNlbGVjdCBmZWF0dXJlcyBoYXZpbmcgbW9yZSB2YXJpYW5jZSBhY3Jvc3Mgc2FtcGxlcyBiZWNhdXNlIHRoZXkgYnJpbmcgbW9yZSBpbmZvcm1hdGlvbi4NCmBgYHtyfQ0KbmYgPC0gMTAwOw0KZm9yKGkgaW4gMTpsZW5ndGgoY29tcGxldGUpKXsNCiAgICANCiAgICBpZHggPC0gY2FyZXQ6Om5lYXJaZXJvVmFyKGNvbXBsZXRlW1tpXV0pDQogICAgbWVzc2FnZShwYXN0ZSgiUmVtb3ZlZCAiLCBsZW5ndGgoaWR4KSwgImZlYXR1cmVzIGZyb20iLCBuYW1lcyhjb21wbGV0ZSlbaV0pKTsNCiAgICBpZihsZW5ndGgoaWR4KSAhPSAwKXsNCiAgICAgICAgY29tcGxldGVbW2ldXSA8LSBjb21wbGV0ZVtbaV1dWywgLWlkeF07DQogICAgfQ0KDQogICAgaWYobmNvbChjb21wbGV0ZVtbaV1dKSA8PSBuZikgbmV4dA0KICAgIA0KICAgIHZhcnMgPC0gYXBwbHkoY29tcGxldGVbW2ldXSwgMiwgdmFyKTsNCiAgICBpZHggPC0gc29ydCh2YXJzLCBpbmRleC5yZXR1cm49VFJVRSwgZGVjcmVhc2luZyA9IFRSVUUpJGl4Ow0KICAgIA0KICAgIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVssIGlkeFsxOm5mXV07DQogICAgDQp9DQpgYGANCg0KU3RhbmRhcmRpemUgZmVhdHVyZXMgd2l0aCB6LXNjb3JlDQpgYGB7cn0NCnpzY29yZSA8LSBmdW5jdGlvbihkYXRhKXsNCiAgICANCiAgICB6c2NvcmVfdmVjIDwtIGZ1bmN0aW9uKHgpIHsgcmV0dXJuICgoeCAtIG1lYW4oeCkpIC8gc2QoeCkpfQ0KICAgIGRhdGEgPC0gYXBwbHkoZGF0YSwgMiwgenNjb3JlX3ZlYykNCiAgICANCiAgICANCiAgICByZXR1cm4oZGF0YSkNCn0NCg0KY29tcGxldGUgPC0gbGFwcGx5KGNvbXBsZXRlLCB6c2NvcmUpOw0KYGBgDQpDbGVhbiBiYXJjb2RlcyByZXRhaW5pbmcgb25seSAiUHJvamVjdC1UU1MtUGFydGljaXBhbnQiIChmaXJzdCAxMiBjaGFyYWN0ZXJzKQ0KYGBge3J9DQpmb3IodiBpbiAxOmxlbmd0aChjb21wbGV0ZSkpew0KICAgIHJvd25hbWVzKGNvbXBsZXRlW1t2XV0pIDwtIHN1YnN0cihyb3duYW1lcyhjb21wbGV0ZVtbdl1dKSwgMSwgMTIpOw0KfQ0KYGBgDQojIERvd25sb2FkIGRpc2Vhc2Ugc3VidHlwZXMNCmBgYHtyfQ0Kc3VidHlwZXMgPC0gYXMuZGF0YS5mcmFtZShUQ0dBYmlvbGlua3M6OlBhbkNhbmNlckF0bGFzX3N1YnR5cGVzKCkpDQoNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW3N1YnR5cGVzJGNhbmNlci50eXBlID09ICJQUkFEIiwgXTsNCiMgUmV0YWluIG9ubHkgcHJpbWFyeSBzb2xpZCB0dW1vcnMgYW5kIHNlbGVjdCBzYW1wbGVzIGluIGNvbW1vbiB3aXRoIG9taWNzIGRhdGENCiMgKGluIHRoZSBzYW1lIG9yZGVyKToNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW1RDR0F1dGlsczo6VENHQXNhbXBsZVNlbGVjdChzdWJ0eXBlcyRwYW4uc2FtcGxlc0lELCAiMDEiKSwgXTsNCnN1Yl9zZWxlY3QgPC0gc3Vic3RyKHN1YnR5cGVzJHBhbi5zYW1wbGVzSUQsMSwxMikgJWluJSByb3duYW1lcyhjb21wbGV0ZVtbMV1dKTsNCnN1YnR5cGVzIDwtIHN1YnR5cGVzW3N1Yl9zZWxlY3QsIF07DQpgYGANCldlIGNvbnNpZGVyIG9ubHkgc2FtcGxlcyBpbiB0aGUgb21pY3MgZGF0YSBpbiBgYGBjb21wbGV0ZWBgYCBmb3Igd2hpY2ggYWxzbyBzdWJ0eXBlIGRhdGEgaXMgcHJlc2VudCBpbiBgYGBzdWJ0eXBlc2BgYA0KYGBge3J9DQpyb3duYW1lcyhzdWJ0eXBlcykgPC0gc3Vic3RyKHN1YnR5cGVzJHBhbi5zYW1wbGVzSUQsIDEsIDEyKTsNCmZvciAoaSBpbiAxOmxlbmd0aChjb21wbGV0ZSkpDQogIGNvbXBsZXRlW1tpXV0gPC0gY29tcGxldGVbW2ldXVtyb3duYW1lcyhzdWJ0eXBlcyksXQ0KIyBQcmludCBudW1iZXIgb2Ygc2FtcGxlcyBmb3IgZWFjaCBzdWJ0eXBlOg0KdGFibGUoc3VidHlwZXMkU3VidHlwZV9JbnRlZ3JhdGl2ZSk7DQpgYGANCiMjIENoZWNrIHN1YnR5cGUgJiBvbWljcyBkYXRhIG9yZGVyDQpgYGB7cn0NCmNvdW50IDwtIDANCmZvcihpIGluIDE6bGVuZ3RoKHJvd25hbWVzKHN1YnR5cGVzKSkpew0KICBpZihyb3duYW1lcyhzdWJ0eXBlcylbaV0gIT0gcm93bmFtZXMoY29tcGxldGVbWzFdXSlbaV0pDQogICAgIGNvdW50IDwtIGNvdW50ICsgMQ0KfQ0KY291bnQNCmBgYA0KQWxsIHBhdGllbnRzL3NhbXBsZXMgYXJlIGluIHRoZSBzYW1lIG9yZGVyIGluIGJvdGggdGhlIGRhdGFzZXRzLg0KIyBNdWx0aS1vbWljcyBkYXRhIGludGVncmF0aW9uDQpTaW1pbGFyaXR5IG1hdHJpY2VzIGZvciBlYWNoIGRhdGEgc291cmNlIHVzaW5nIGV4cG9uZW50aWFsIGV1Y2xpZGlhbiBkaXN0YW5jZSAoYWZmaW5pdHkgbWF0cml4KS4NCmBgYHtyfQ0KV19saXN0IDwtIGxpc3QoKTsNCmZvcihpIGluIDE6bGVuZ3RoKGNvbXBsZXRlKSl7DQogICAgRGlzdCA8LSAoZGlzdDIoYXMubWF0cml4KGNvbXBsZXRlW1tpXV0pLCBhcy5tYXRyaXgoY29tcGxldGVbW2ldXSkpKV4oMS8yKQ0KICAgIFdfbGlzdFtbaV1dIDwtIGFmZmluaXR5TWF0cml4KERpc3QpDQp9DQpgYGANCiMjIEludGVncmF0aW9uIHRocm91Z2ggU05GDQpJbnRlZ3JhdGlvbiBvZiB0aGUgbWF0cmljZXMgdXNpbmcgU2ltaWxhcml0eSBOZXR3b3JrIEZ1c2lvbg0KKl90XyBudW1iZXIgb2YgaXRlcmF0aW9ucw0KKl9LXyBudW1iZXIgb2YgbmVpZ2hib3VycyB0byBjb25zaWRlciB0byBjb21wdXRlIGxvY2FsIHNpbWlsYXJpdHkgbWF0cml4DQoNCmBgYHtyfQ0KV19pbnRfU05GIDwtIFNORihXX2xpc3QsIEs9MjAsIHQ9MjApOw0KYGBgDQojIyBJbnRlZ3JhdGlvbiB0aHJvdWdoIGF2ZXJhZ2UNCkludGVncmF0aW9uIHRocm91Z2ggYXZlcmFnZSBvZiBtYXRyaWNlcw0KYGBge3J9DQpXX2ludF9tZWFuIDwtIFJlZHVjZSgnKycsIFdfbGlzdCkvbGVuZ3RoKFdfbGlzdCkNCmBgYA0KYGBge3J9DQpmb3IgKGkgaW4gMTpsZW5ndGgoV19saXN0KSkNCiAgICBwbG90KFdfbGlzdFtbaV1dLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQoNCmBgYHtyfQ0KcGxvdChXX2ludF9tZWFuLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQpgYGB7cn0NCnBsb3QoV19pbnRfU05GLHhsaW09YygwLDAuMDEpLHlsaW09YygwLDAuMDEpKQ0KYGBgDQojIERpc2Vhc2Ugc3VidHlwZSBkaXNjb3Zlcnkgd2l0aCBQQU0NCk51bWJlciBvZiBjbHVzdGVycy4NCmBgYHtyfQ0KayA8LSBsZW5ndGgodW5pcXVlKHN1YnR5cGVzJFN1YnR5cGVfSW50ZWdyYXRpdmUpKTsNCmBgYA0KIyMgRWFjaCBkYXRhIHNvdXJjZQ0KQ29udmVydCBzaW1pbGFyaXR5IG1hdHJpeCBpbnRvIGEgZGlzdGFuY2UgbWF0cml4LiBUaGUgc2ltaWxhcml0aWVzIGFyZSBub3JtYWxpemVkIGluIHRoZSByYW5nZSAmXGxlZnRbMCwgMVxyaWdodF0kIHVzaW5nIG1pbi1tYXggbm9ybWFsaXphdGlvbiBiZWZvcmUgY29udmVyc2lvbiBpbnRvIGRpc3RhbmNlcy4NCmBgYHtyfQ0KZGlzdCA8LSBsaXN0KCkNCkQgPC0gbGlzdCgpDQpmb3IgKGkgaW4gMTpsZW5ndGgoKFdfbGlzdCkpKXsNCiAgZGlzdFtbaV1dIDwtIDEgLSBOZXRQcmVQcm9jOjpNYXguTWluLm5vcm0oV19saXN0W1tpXV0pDQogIERbW2ldXSA8LSBhcy5kaXN0KGRpc3RbW2ldXSkNCn0NCmZvciAoaSBpbiAxOmxlbmd0aCgoV19saXN0KSkpDQogIHBhbS5yZXMgPC0gcGFtKERbW2ldXSwgaz1rKQ0KYGBgDQojIyBJbnRlZ3JhdGVkIGRhdGEgdGhyb3VnaCBtZWFuDQpgYGB7cn0NCmRpc3RfbWVhbiA8LSAxIC0gTmV0UHJlUHJvYzo6TWF4Lk1pbi5ub3JtKFdfaW50X21lYW4pOw0KRF9tZWFuIDwtIGFzLmRpc3QoZGlzdF9tZWFuKTsgDQoNCnBhbS5yZXMgPC0gcGFtKERfbWVhbiwgaz1rKTsNCmBgYA0KIyMgSW50ZWdyYXRlZCBkYXRhIHRocm91Z2ggU05GDQpgYGB7cn0NCmRpc3RfU05GIDwtIDEgLSBOZXRQcmVQcm9jOjpNYXguTWluLm5vcm0oV19pbnRfU05GKTsNCkRfU05GIDwtIGFzLmRpc3QoZGlzdF9TTkYpOyANCg0KIyBBcHBseSBjbHVzdGVyaW5nIGFsZ29yaXRobXMgb24gaW50ZWdyYXRlZCBtYXRyaXg6DQpwYW0ucmVzIDwtIHBhbShEX1NORiwgaz1rKTsNCmBgYA0KI0Rpc2Vhc2Ugc3VidHlwZSBkaXNjb3Zlcnkgd2l0aCBzcGVjdHJhbCBjbHVzdGVyaW5nDQooQ29uc2lkZXIgZGlzdGFuY2UgbWF0cml4IGNhbGN1bGF0ZWQgYWJvdmUpDQojIyBJbnRlZ3JhdGVkIGRhdGEgdGhyb3VnaCBTTkYNCmBgYHtyfQ0KayA8LSBsZW5ndGgodW5pcXVlKHN1YnR5cGVzJFN1YnR5cGVfSW50ZWdyYXRpdmUpKTsNCnNjLnJlcyA8LSBTTkZ0b29sOjpzcGVjdHJhbENsdXN0ZXJpbmcoV19pbnRfU05GLCBLPWspDQojdG8gaGF2ZSB1bmlmb3JtIHR5cGUNCnBhbS5zYy5yZXMgPC0gcGFtKHNjLnJlcyxrPWspDQpgYGANCg0KDQpgYGB7cn0NCnNlc3Npb25JbmZvKCkNCmBgYA0KDQo=